package leetcode.offer;

import leetcode.base.ListNode;

public class IsPalindromeList {
    public boolean isPalindrome(ListNode head) {
        if(head == null) {
            return false;
        }

        ListNode mid = mid(head);
        ListNode reverseNode = reverse(mid);
        ListNode p = head;
        while (reverseNode != null) {
            if(p.val == reverseNode.val) {
                p = p.next;
                reverseNode = reverseNode.next;
            } else {
                return false;
            }
        }

        return true;
    }


    public ListNode mid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) {
            return slow.next;
        } else {
            return slow;
        }
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
